package answerQueries;

import java.util.Arrays;

public class Solution {
    public int[] answerQueries(int[] nums, int[] queries) {
//        int m = queries.length;
//        int[] ans = new int[m];
//        int[][] marks = new int[m][2];
//        for (int i = 0; i < m; i++) {
//            marks[i][0] = i;
//            marks[i][1] = queries[i];
//        }
//        int sum = 0;
//        Arrays.sort(nums);
//        Arrays.sort(marks,(o1,o2)->o1[1] - o2[1]);
//        // 每次都选最小的几个数字
//        for (int i = 0,j = 0; i < m; i++) {
//            while (j<nums.length&&sum+nums[j]<=marks[i][1]) {
//                sum+=nums[j];
//                j++;
//            }
//            ans[marks[i][0]] = j;
//        }
//        return ans;

        // 二分查找 找和小于等于target的下标
        // 前缀和
        Arrays.sort(nums);
        for (int i = 1; i < nums.length; i++) {
            nums[i]+=nums[i-1];
        }
        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            ans[i] = binarySearch(nums,queries[i]);
        }
        return ans;
    }
    private int binarySearch(int[] nums,int sum) {
        int l = 0,r = nums.length-1;
        while (l<=r) {
            int mid = (l+r)>>1;
            if(mid>sum) {
                r = mid-1;
            }else {
                l = mid+1;
            }
        }
        return l;
    }
}
